#pragma once

#include <vector>
#include <algorithm>
#include <iterator>

namespace mdtx::online::algo
{
    /**
     * @brief Find mode of SORTED data
     *
     */
    class mode
    {
    public:
        /**
         * @brief Run the algo
         *
         * @tparam iter input iterator type
         * @param it iterator to begin of SORTED input data
         * @param n number of data
         * @return auto
         */
        template <typename iter>
        static auto run(iter it, ptrdiff_t n)
        {
            using value_type = typename std::iterator_traits<iter>::value_type;

            value_type width, min_width, d1, d2;
            ptrdiff_t mid, left, right, i, j;

            auto get = [it](ptrdiff_t idx) -> decltype(auto)
            {
                return *(it + idx);
            };

            left = 0;
            right = n - 1;
            while (true)
            {
                auto m = right - left + 1;
                if (m == 1)
                {
                    return get(left);
                }
                else if (m == 2)
                {
                    return (get(left) + get(right)) / 2;
                }
                else if (m == 3)
                {
                    d1 = get(left + 1) - get(left);
                    d2 = get(right) - get(left + 1);
                    if (d1 < d2)
                    {
                        return (get(left) + get(left + 1)) / 2;
                    }
                    else if (d1 > d2)
                    {
                        return (get(left + 1) + get(right)) / 2;
                    }
                    else
                    {
                        return get(left + 1);
                    }
                }
                else
                {
                    min_width = get(right) - get(left);
                    mid = (m + 1) / 2;
                    j = left;
                    for (i = left; i < left + m - mid; ++i)
                    {
                        width = get(i + mid - 1) - get(i);
                        if (width < min_width)
                        {
                            min_width = width;
                            j = i;
                        }
                    }
                    left = j;
                    right = j + mid - 1;
                }
            }
        }
    };
}
